package dstbsort;

import utils.FileUtils;
import utils.SortUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

//分布式希尔排序
public class DstbShellSort {
    public static void main(String[] args) throws Exception {
        // 需要加载的排序的文件，n-普通版本，数据范围在int范围内，1k - 1000个数据的文件
//        String fileName = "n_1k";
//		String fileName = "n_1w";
//		String fileName = "n_10w";
        String fileName = "n_100w";
//        String fileName = "n_500w";

        // 数据文件加载
        long startTime = System.currentTimeMillis();
        String readText = FileUtils.readText(SortUtils.FILE_PREFIX + fileName);
        String[] numString = readText.split(" ");
        int[] arr = new int[numString.length];
        for (int i = 0; i < numString.length; i++) {
            arr[i] = Integer.valueOf(numString[i]);
        }
        long endTime = System.currentTimeMillis();
        System.out.println(fileName + "数据文件加载共耗时：" + (endTime - startTime) + "ms");

        // 用多线程实现基数排序
        startTime = System.currentTimeMillis();
        dstbShellSort(arr);
        endTime = System.currentTimeMillis();
        System.out.println(fileName + "多线程希尔排序共耗时：" + (endTime - startTime) + "ms");

        // 正确性验证
        startTime = System.currentTimeMillis();
        SortUtils.validate(arr);
        endTime = System.currentTimeMillis();
        System.out.println(fileName + "希尔排序正确性验证共耗时：" + (endTime - startTime) + "ms");
    }

    private static void dstbShellSort(int[] arr) throws Exception {
        ExecutorService threadPool = Executors.newCachedThreadPool();
        int gap = arr.length;
        while (gap != 1) {
            gap = gap / 2;
            //使用CountDownLatch，保证gap个线程都操作完成之后，在进入下一轮迭代。
            CountDownLatch latch = new CountDownLatch(gap);
            for (int i = 0; i < gap; i++) {
                threadPool.submit(new DstbShellTask(arr, i, gap, latch));
            }
            latch.await();
        }
        threadPool.shutdown();
        threadPool.awaitTermination(Integer.MAX_VALUE, TimeUnit.MILLISECONDS);
    }

    public static class DstbShellTask implements Runnable {
        int[] num;
        int start;
        int gap;
        CountDownLatch latch;

        public DstbShellTask(int[] num, int start, int gap, CountDownLatch latch) {
            this.num = num;
            this.start = start;
            this.gap = gap;
            this.latch = latch;
        }

        @Override
        public void run() {
            int flag = 0;
            do {
                flag = 0;
                for (int k = start + gap; k < num.length; k += gap) {
                    if (num[k] < num[k - gap]) {
                        int temp = num[k];
                        num[k] = num[k - gap];
                        num[k - gap] = temp;
                        flag = 1;
                    }
                }
            } while (flag == 1);
            latch.countDown();
        }
    }
}
